#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

/*****定义结构体*****/
struct btnode
{
    char data;
    struct btnode *lc, *rc;
}; //*btnode, *btree;
typedef struct btnode btnode;
typedef struct btnode *btree;
/*****定义结构体*****/

/*****找到父节点*****/
btree findF(btree target, btree root)
{
    if (root != nullptr && target == root || root == nullptr || target == nullptr)
    {
        return nullptr;
    }
    else
    {
        if (target == root->lc || target == root->rc)
        {
            return root;
        }
        btree ln = findF(target, root->lc);
        btree rn = findF(target, root->rc);
        if (ln != nullptr)
        {
            return ln;
        }
        if (rn != nullptr)
        {
            return rn;
        }
    }
    return nullptr;
}
/*****找到父节点*****/

/*****打印二叉树*****/
void print_t(btree t)
{
    if (t != NULL)
    {
        printf("当前结点为%c   ", t->data);
        if (t->lc != NULL)
        {
            printf("左结点为%c    ", t->lc->data);
        }
        else
        {
            printf("左结点为空   ");
        }
        if (t->rc != nullptr)
        {
            printf("右结点为%c\n", t->rc->data);
        }
        else
        {
            printf("右结点为空\n");
        }
        if (t->lc != nullptr)
        {
            print_t(t->lc);
        }
        if (t->rc != nullptr)
        {
            print_t(t->rc);
        }
    }
    else
    {
        printf("二叉树为空！\n");
    }
}
/*****打印二叉树*****/

/*****核心功能函数*****/
void bt2ie_temp(btree p, int depth, btree root)
{
    if (p == NULL)
    {
        printf("二叉树为空！"); //根结点为空，说明是个空树
    }
    else if (p->lc == NULL && p->rc == NULL) //叶子结点均为操作数
    {
        printf("%c", p->data); //输出操作数（不需要加括号）
    }
    else
    {
        if (depth > 1)
        {
            if (p->data != '*' && p->data != '/')
            {
                btree temp = findF(p, root);
                if (temp->rc == p)
                {
                    printf("("); //还有子表达式，要加括号
                }
                if (temp->lc == p)
                {
                    if (temp->data == '*' || temp->data == '/')
                    {
                        printf("(");
                    }
                }
            }
            else
            {
                btree temp = findF(p, root);
                if (temp->rc == p && temp->data != '+' && temp->data != '-')
                {
                    printf("(");
                }
            }
        }
        bt2ie_temp(p->lc, depth + 1, root); //递归调用遍历左边
        printf("%c", p->data);
        bt2ie_temp(p->rc, depth + 1, root);
        if (depth > 1)
        {
            if (p->data != '*' && p->data != '/')
            {
                btree temp = findF(p, root);
                if (temp->rc == p)
                {
                    printf(")"); //还有子表达式，要加括号
                }
                if (temp->lc == p)
                {
                    if (temp->data == '*' || temp->data == '/')
                    {
                        printf(")");
                    }
                }
            }
            else
            {
                btree temp = findF(p, root);
                if (temp->rc == p && temp->data != '+' && temp->data != '-')
                {
                    printf(")");
                }
            }
        }
    }
}

void bt2ie(btree root) // infix expression
{
    print_t(root);
    printf("\n");
    bt2ie_temp(root, 1, root); //根结点的高度为1
    printf("\n");
}
/*****核心功能函数*****/

/*****声明二叉树结点*****/
btree t0, t1, t2, t3, t4, t5, t6, t7, t8, t9, t10, t11, t12, t13;
/*****声明二叉树结点*****/

/*****初始化二叉树*****/
void t_init()
{
    t1->lc = nullptr;
    t1->rc = nullptr;
    t2->lc = nullptr;
    t2->rc = nullptr;
    t3->lc = nullptr;
    t3->rc = nullptr;
    t4->lc = nullptr;
    t4->rc = nullptr;
    t5->lc = nullptr;
    t5->rc = nullptr;
    t6->lc = nullptr;
    t6->rc = nullptr;
    t7->lc = nullptr;
    t7->rc = nullptr;
    t8->lc = nullptr;
    t8->rc = nullptr;
    t9->lc = nullptr;
    t9->rc = nullptr;
    t10->lc = nullptr;
    t10->rc = nullptr;
    t11->lc = nullptr;
    t11->rc = nullptr;
    t12->lc = nullptr;
    t12->rc = nullptr;
    t13->lc = nullptr;
    t13->rc = nullptr;
}
/*****初始化二叉树*****/

/*****主函数*****/
int main()
{
    t0 = NULL;
    t1 = (btree)malloc(sizeof(btnode));
    t2 = (btree)malloc(sizeof(btnode));
    t3 = (btree)malloc(sizeof(btnode));
    t4 = (btree)malloc(sizeof(btnode));
    t5 = (btree)malloc(sizeof(btnode));
    t6 = (btree)malloc(sizeof(btnode));
    t7 = (btree)malloc(sizeof(btnode));
    t8 = (btree)malloc(sizeof(btnode));
    t9 = (btree)malloc(sizeof(btnode));
    t10 = (btree)malloc(sizeof(btnode));
    t11 = (btree)malloc(sizeof(btnode));
    t12 = (btree)malloc(sizeof(btnode));
    t13 = (btree)malloc(sizeof(btnode));

    /***空二叉树***/
    printf("/*****空二叉树*****/\n");
    t_init();
    bt2ie(t0);
    printf("/*****空二叉树*****/\n\n\n\n");
    /***空二叉树***/

    /***第1棵非空二叉树***/
    printf("/*****第1棵非空二叉树*****/\n");
    t_init();
    t1->data = '-';
    t1->lc = t2;
    t1->rc = t3;
    t2->data = '+';
    t2->lc = t4;
    t2->rc = t5;
    t3->data = '/';
    t3->lc = t6;
    t3->rc = t7;
    t4->data = 'a';
    t5->data = '*';
    t5->lc = t8;
    t5->rc = t9;
    t6->data = 'e';
    t7->data = 'f';
    t8->data = 'b';
    t9->data = '-';
    t9->lc = t10;
    t9->rc = t11;
    t10->data = 'c';
    t11->data = 'd';
    bt2ie(t1);
    printf("/*****第1棵非空二叉树*****/\n\n\n\n");
    /***第1棵非空二叉树***/

    /***第2棵非空二叉树***/
    printf("/*****第2棵非空二叉树*****/\n");
    t_init();
    t1->data = '+';
    t1->lc = t2;
    t1->rc = t3;
    t2->data = 'a';
    t3->data = '*';
    t3->lc = t4;
    t3->rc = t5;
    t4->data = '+';
    t4->lc = t6;
    t4->rc = t7;
    t5->data = '-';
    t5->lc = t8;
    t5->rc = t9;
    t6->data = 'b';
    t7->data = 'c';
    t8->data = 'd';
    t9->data = 'e';
    bt2ie(t1);
    printf("/*****第2棵非空二叉树*****/\n\n\n\n");
    /***第2棵非空二叉树***/

    /***第3棵非空二叉树***/
    printf("/*****第3棵非空二叉树*****/\n");
    t_init();
    t1->data = '+';
    t1->lc = t2;
    t1->rc = t3;
    t2->data = 'a';
    t3->data = '+';
    t3->lc = t4;
    t3->rc = t5;
    t4->data = '+';
    t4->lc = t6;
    t4->rc = t7;
    t5->data = '-';
    t5->lc = t8;
    t5->rc = t9;
    t6->data = 'b';
    t7->data = 'c';
    t8->data = 'd';
    t9->data = 'e';
    bt2ie(t1);
    printf("/*****第3棵非空二叉树*****/\n\n\n\n");
    /***第3棵非空二叉树***/

    /***第4棵非空二叉树***/
    printf("/*****第4棵非空二叉树*****/\n");
    t_init();
    t1->data = '+';
    t1->lc = t2;
    t1->rc = t3;
    t2->data = 'a';
    t3->data = '+';
    t3->lc = t4;
    t3->rc = t5;
    t4->data = '+';
    t4->lc = t6;
    t4->rc = t7;
    t5->data = '-';
    t5->lc = t8;
    t5->rc = t9;
    t6->data = 'b';
    t7->data = 'c';
    t8->data = '+';
    t8->lc = t10;
    t8->rc = t11;
    t9->data = '*';
    t9->lc = t12;
    t9->rc = t13;
    t10->data = 'd';
    t11->data = 'e';
    t12->data = 'f';
    t13->data = 'd';
    bt2ie(t1);
    printf("/*****第4棵非空二叉树*****/\n\n\n\n");
    /***第4棵非空二叉树***/

    /***第5棵非空二叉树***/
    printf("/*****第5棵非空二叉树*****/\n");
    t_init();
    t1->data = '+';
    t1->lc = t2;
    t1->rc = t3;
    t2->data = 'a';
    t3->data = '/';
    t3->lc = t4;
    t3->rc = t5;
    t4->data = '+';
    t4->lc = t6;
    t4->rc = t7;
    t5->data = '/';
    t5->lc = t8;
    t5->rc = t9;
    t6->data = 'b';
    t7->data = 'c';
    t8->data = '+';
    t8->lc = t10;
    t8->rc = t11;
    t9->data = '*';
    t9->lc = t12;
    t9->rc = t13;
    t10->data = 'd';
    t11->data = 'e';
    t12->data = 'f';
    t13->data = 'g';
    bt2ie(t1);
    printf("/*****第5棵非空二叉树*****/\n\n\n\n");
    /***第5棵非空二叉树***/

    system("pause");
}
/*****主函数*****/